package com.data.basic.chapter13;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 *红黑树：与平衡二叉树一样，都是一种二叉搜索树；
 *  是一颗 ”黑“ 平衡的二叉树，左右子树的黑色节点绝对平衡
 */
public class RBTree<K extends Comparable<K>,V> {
    /**
     * 添加元素
     * {不包括重复的元素，如果要包括重复元素的话，那么定义：左子树小于等于节点，或者右子树大于等于节点}
     *  将null当成空树
     */
    public void add(K k,V v){
        root = add(root,k,v);
        root.color=BLACK;//保持根节点是黑色的
    }
    /**
     * 1.递归终止的条件
     */
// 向以node为根的红黑树中插入元素E，递归算法
// 返回插入新节点后红黑树的根------->将节点挂在红黑树下
    private Node add(Node node, K k,V v) {
//        1.递归终止的条件
        if (node==null){
            size++;
            return new Node(k,v);//默认生成红色节点
        }
//      执行递归  重复元素不再添加
        if (k.compareTo(node.key)<0){
            node.left =  add(node.left,k,v);
        }else if(k.compareTo(node.key)>0){
            node.right = add(node.right,k,v);
        }
        //红黑树性质的维护链   操作顺序不能改
        // 红黑树最复杂的情况就是平衡二叉树里面的LR操作，因为红色节点只能向左倾斜，所以没有RL操作。
        // 其它的维护情况都是这个过程的子类的，所以直接当成LR的情况情形处理
/**
 * ---------------------------------------------------------------------------------------------------
 *      LR的情况
 *        {42B}                   {42B}                 {40B}                     {40R}
 *       /   \     左旋            /  \    右旋          /  \       颜色翻转        /   \
 *    {37R}  T2   ---------->  {40R}  T2 --------->   {37R} {42R}  ------->    {37B}  {42B}
 *    /  \                      /  \                  / \    /  \               / \    /  \
 *   T1   {40R}              {37R} T4                T1 T3  T4  T2             T1 T3  T4  T2
 *         /  \              /  \
 *        T3  T4           T1   T3
 *
 *红黑树的维护链
 * ---------------------------------------------------------------------------------------------------
 *
 *
 *
 *
 *
  */

        if (isRed(node.right)&&!isRed(node.left)){
            //左旋
            node =  leftRotate(node);
        }
        if (isRed(node.left)&&isRed(node.left.left)){
            //右旋，然后再进行颜色翻转
            node = rightRotate(node);
        }
        if(isRed(node.right)&&isRed(node.left)){
            //颜色反转
         flipColors(node);

        }
        return node;

    }

    /**
     * 红黑树的左旋:当红色节点出现在右边的情况
     *
     左旋：插入节点{RED x}（2-节点的情况 ：插入的永远是红色节点，下面是插入的值大于根节点的情况）

     node.right = x.left                x.color = node.color
     x.left = node                     node.color = RED

     {BLANK node}                           {RED x}                       {BLANK x}
     /    \              左旋               /     \        换颜色          /      \
     T1    {RED x}         ------->    {BLANK node}  T3     -------->   {RED node}   T3
     /   \                           /   \                           /  \
     T2    T3                        T1    T2                        T1   T2
     */
    private Node leftRotate(Node node){
        Node x = node.right;
        //左旋转
        node.right =x.left;
        x.left = node;
        x.color = node.color;
        node.color = RED;

        return x;
    }
    /**
     * 颜色反转：插入的是4-节点的情况或者说是，两个叶子结点都是红色的情况
     */
    private void flipColors(Node node){
        node.color=RED;
        node.right.color=BLACK;
        node.left.color=BLACK;
    }
    /**
     * 右旋
     *     右旋：插入节点 {RED}：
     *     node.left = T1;                                     x.color = node.color
     *     x.right = node;                                     node.color = RED//因为这里的需要融合，所以颜色要改为RED
     *     {BLANK node}                     {RED x}                                {BLANK x}
     *     /    \            右旋           /     \                  换颜色          /      \          颜色反转
     *   {RED x}    T2     ------->       {RED} {BLANK node}       -------->     {RED}   {RED node}  ------------>正常
     *    /   \                                   /   \                                     /  \
     *  {RED}  T1                                 T1    T2                                  T1   T2
     */
    private Node rightRotate(Node node){
        Node  x  = node.left;

        //右旋
        node.left=x.right;
        x.right = node;
        x.color=node.color;
        node.color=RED;
        return x;

    }



    /**
     * 查询元素
     * @param e
     * @return
     */
    public boolean contains(K e){
        return contains(root,e);
    }

    private boolean contains(Node node, K k) {
        if (node==null){// 1.递归终止条件
            return false;
        }
        if (k.compareTo(node.key)==0){//2.操作数和递归量的变化
            return true;
        }else if (k.compareTo(node.key)>0){
            return  contains(node.right,k);
        }else                                   //(e.compareTo(node.e)<0)
        {
            return contains(node.left,k);
        }

    }
    /**
     * 二叉树的前序遍历
     */

    public void preOrder(){
        preOrder(root);

    }
    /**
     *  前序遍历以node为根的二叉搜索树，递归算法
     */

    private void preOrder(Node node) {
        if (node==null){//1.递归终止条件
            return;
        }
        // 2.递归逻辑
        System.out.println(node.key);
        preOrder(node.left);
        preOrder(node.right);
    }
    /**
     * 前序遍历 ----->非递归算法，栈的应用
     */
    public void preOrderNR(){

        Stack<Node> stack = new Stack<Node>();

        stack.push(root);
        while(!stack.isEmpty()){
            Node cur = stack.pop();
            System.out.println(cur.key);


            // 注意这里的  要右子树先进栈，左子树在进栈
            if (cur.right!=null){
                stack.push(cur.right);
            }

            if (cur.left!=null){
                stack.push(cur.left);
            }
        }


    }

    /**
     * 中序遍历-----》递归
     *
     */
    public void inOrder(){
        inOrder(root);
    }

    private void inOrder(Node node) {
        if (node==null){
            return;
        }
        inOrder(node.left);
        System.out.println(node.key);
        inOrder(node.right);

    }

    /**
     * 非递归的方式   ----->实现中序排序
     */
    public void inOrderNR(){

        if (root==null){return;}
        Stack<Node>  stack=new Stack<Node>();
        while (root!=null||!stack.isEmpty()){
            while(root!=null){
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            System.out.println(root.key);
            root = root.right;
        }
    }

    /**
     * 后序遍历
     */

    public void postOrder(){
        postOrder(root);
    }

    /**
     * 后序遍历以node为节点的二分搜索树，递归算法
     *
     * 应用：为二分搜索树释放空间
     * @param node
     */
    private void postOrder(Node node) {
        if (node==null){
            return;
        }
        postOrder(node.left);
        postOrder(node.right);
        System.out.println(node.key);
    }

    /**
     * 层序遍历的实现--------> 队列完成
     */

    public void levelOrder(){
        Queue<Node> queue = new LinkedList<Node>();
        queue.add(root);
        while(!queue.isEmpty()){
            Node cur = queue.remove();
            System.out.println(cur.key);

            if (cur.left!=null){
                queue.add(cur.left);
            }
            if (cur.right!=null){
                queue.add(cur.right);
            }
        }

    }



    /**
     * 二叉搜索树的删除
     * 注意：最大值在最右边，最小值在最左边
     */

    /**
     * 查找最小元素
     * @return
     */
    public K minimum(){
        if (size==0){
            throw new IllegalArgumentException("BST is empty");
        }
        return minimum(root).key;

    }
    /**
     * 查找最大元素
     */

    public K maximum(){
        if (size==0){
            throw new IllegalArgumentException("BST is empty");
        }
        return maximum(root).key;
    }

    private Node maximum(Node node) {
        if (node.right==null){
            return node;
        }
        return  maximum(node.right);
    }

    private Node minimum(Node node) {
        // 递归实现链表的最小值
//        if (node.left==null){
//            return node;
//        }
//        return  minimum(node.left);

        // 非递归实现链表的最小值
        Node temp=null;
        while(node!=null){

            if (node.left==null){
                temp = node;
            }
            node = node.left;
        }
        return temp;
    }

    /**
     * 删除二分搜索树的最小元素
     */
    public K removeMin(){
        K ret = minimum();
        root = removeMin(root);
        return ret;
    }



    /**
     * 删除掉以node为根的二分搜索树中的最小节点
     * 返回删除节点后新的二分搜索树的根
     */
    private Node removeMin(Node node) {
        if (node.left==null){
            Node rightNode = node.right;
            node.right = null;
            size--;
            return rightNode;// 返回最小元素的右子树
        }
        node.left = removeMin(node.left);// 将最小元素的右孩子直接赋值给最小元素节点的父亲节点
        return node;

    }

    /**
     *  删除二叉搜索树的最大值
     */
    public K removeMax(){
        K ret = maximum();
        root = removeMax(root);

        return ret;

    }
    /**
     * 删除掉以node为根的二分搜索树中的最大节点
     * 返回删除节点后新的二分搜索树的根
     */
    private Node removeMax(Node node) {

        if (node.right==null){
            Node leftNode = node.left;
            node.left=null;
            size--;
            return leftNode;

        }
        node.right = removeMax(node.right);
        return node;
    }

    /**
     * 从二分搜索树中删除元素为e的节点
     */
    public void remove(K k){
        root = remove(root,k);

    }
    /**
     *   删除以node为根的二分搜索树中值为e的节点，递归算法
     *   返回删除节点后新的二叉树的根
     */

    private Node remove(Node node, K k) {
        if (node == null){
            return null;
        }
        if (k.compareTo(node.key)<0){// 先进行查找，找到待删除的节点
            node.left = remove(node.left,k);
            return node;
        }
        else if(k.compareTo(node.key)>0){
            node.right = remove(node.right,k);
            return node;
        }
        else{//e = node.e   删除节点 ---->分情况讨论
            if (node.left==null){
                Node rightNode = node.right;
                node.right = null;
                size--;
                return rightNode;// 返回右子树
            }
            if (node.right ==null){
                Node leftNode = node.left;
                node.left = null;
                size--;
                return leftNode;// 返回左子树
            }
// 寻找右子树的最小值来替换这里的要删除的节点
            Node successor = minimum(node.right);
            successor.right = removeMin(node.right);
            size++;// removeMin赋值给了successor，所以要加回来
            successor.left = node.left;


            node.left = node.right = null;
            size--;// 删除了节点的联系

            return successor;

        }


    }

    private static final boolean RED = true;
    private static final boolean BLACK = false;
    private class Node{
        /**
         * 二分搜索树的节点类
         */
        public K key;
        public V value;
        public Node left,right;
        public boolean color;

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
            this.left=null;
            this.right=null;
            color=RED;//因为在2-3树中添加节点，本身就需要和叶子结点融合，因为red节点和其父亲节点，在2-3树中代表着一个3-节点
        }
    }

    private Node root;
    private int size;

    public RBTree() {
        root = null;
        size=0;
    }

    public int getSize() {
        return size;
    }

    public boolean isEmpty(){
        return size==0;
    }

    /**
     * 如果节点为null，那么就是空节点
     * @param node
     * @return
     */
    public boolean isRed(Node node){
        if (node==null){
            return BLACK;
        }
        return node.color;
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        generateBSTString(root,0,res);
        return res.toString();
    }
    //
    private void generateBSTString(Node node, int depth, StringBuilder res) {
        if (node==null){
            res.append(generateDepthString(depth)+"null\n");
            return;
        }
        // 基于递归的toString方法
        res.append(generateDepthString(depth)+node.key+":"+node.value+"\n");
        generateBSTString(node.left,depth+1,res);
        generateBSTString(node.right,depth+1,res);
    }

    private String generateDepthString(int depth) {
        StringBuilder res = new StringBuilder();
        for (int i=0;i<depth;i++){
            res.append("-");
        }
        return res.toString();
    }
}
